(1) Field of the Invention
The present invention relates to an encryption system. More specifically, the present invention relates to an encryption system which has a decreased difference between encryption time and decryption time, and is capable of generating a highly random expansion key.
(2) Description of the Related Art
Due to a rapid spread of digital communication in recent years, a data encryption method for securing data confidentiality through communication is highly demanded for the purpose of protecting privacy and the development of sound industries. In order to realize an encryption method, a speedy encryption process, and easy implementation, and a high security level are required. In a generic structure of such an encryption method, the data subject for encryption is divided into blocks of a specific size, a data scrambling process is executed to each block based on a specific encryption key, and then a ciphertext is generated.
(First Related Art)
As one of such encryption methods, there is Rijndael encryption which is established as the Advanced Encryption Standard (AES). The AES is the next generation standard of encryption in the United States. FIG. 16 is a diagram showing the internal structure of an encryption device using the Rijndael encryption method. The encryption device 1300 includes an expansion key generating unit 6 that generates and outputs 128-bit expansion keys SK0˜SK10 from a 128-bit encryption key EK, and a data scrambling unit 5 that is connected to the expansion key generating unit 6. The data scrambling unit 5 receives the expansion keys SK0˜SK10 from the expansion key generating unit 6, executes a data scramble by repeating a specific data conversion process for a plain text PT of 128-bit data using the expansion keys SK0˜SK10, and generates a 128-bit ciphertext CT.
The expansion key generating unit 6 includes the following elements: a data dividing unit 600 that receives the encryption key EK, divides the encryption key EK into four 32-bit data blocks D0, D1, D2 and D3, and outputs them; a key conversion unit 60 that is connected to the data dividing unit 600, receives the data blocks D0˜D3 from the data dividing unit 600, executes a specific operation, which is explained later, to them, and generates the expansion key SK1 and four 32-bit data blocks, and outputs them; and key conversion units 61˜69, each of which is connected to the preceding key conversion unit, receives four 32 bits data blocks from the key conversion unit, executes a specific operation, which is explained later, to them, generates the expansion key and four 32-bit data blocks, and outputs them.
The expansion keys output from the key conversion units 61˜69 are defined as the expansion keys SK2˜SK10 respectively. Although the key conversion unit 69 outputs four data blocks, they are not used for other processes. In addition, the expansion key generating unit 6 outputs the encryption key EK as the expansion key SK0.
The data scrambling unit 5 includes the following elements: a key adding unit 500, which is connected to the expansion key generating unit 6, where the key adding unit 500 receives the expansion key SK0, executes an exclusive-OR operation per bit between a plain text PT and the expansion key SK0, a data conversion unit 50 connected to the key adding unit 500 and the key conversion unit 60 which converts the data output from the key adding unit 500 based on the expansion key SK1; data conversion units 51˜58 which are connected to the key conversion units 61˜68 respectively, and convert the data output from the preceding data conversion unit based on the expansion keys SK2˜SK9 respectively; and a final data conversion unit 59, which is connected to the data conversion unit 58 and the key conversion unit 69, where the final data conversion unit 59 converts the data output from the data conversion unit 58 based on the expansion key SK10, and outputs a ciphertext CT.
FIG. 17 is a diagram showing the internal structure of the key conversion units 60˜69. Each of the key conversion units 60˜69 executes a key conversion process, which is explained later, based on first˜fourth input data X0˜X3 of 32 bits each, and outputs first˜fourth output data Y0˜Y3 and the 128-bit expansion key SK.
Each of the key conversion units 60˜69 includes the following elements: a data rotation unit 601 that receives the fourth input data X3, executes a rotation bit shift by 8 bits to the input data X3 in an upper bit direction (a left direction), and outputs its result; a data substituting unit 602 that is connected to the data rotation unit 601, receives the operation result from the data rotation unit 601, executes a specific substituting process to the operation result, and outputs its result; and an exclusive-OR operation unit 603, which is connected to the data substituting unit 602, where the exclusive-OR operation unit 603 receives the substitution result from the data substituting unit 602, executes the exclusive-OR operation per bit between the substitution result and a predefined 32-bit constant Rcon, and outputs data T.
Each of the key conversion units 60˜69 further includes the following elements: an exclusive-OR operation unit 604 that is connected to the exclusive-OR operation 603, where the exclusive-OR operation unit 604 receives the first input data X0 and the data T output from the exclusive-OR operation unit 603, executes the exclusive-OR operation per bit between the first input data X0 and the data T, and outputs the first output data Y0; and an exclusive-OR operation unit 605 which is connected to the exclusive-OR operation unit 604, where the exclusive-OR operation unit 605 receives the second input data X1 and the operation result of the exclusive-OR operation unit 604, executes the exclusive-OR operation per bit between the second input data X1 and the operation result, and outputs the second output data Y1.
Each of the key conversion units 60˜69 further includes: an exclusive-OR operation unit 606 which is connected to the exclusive-OR operation unit 605, where the exclusive-OR operation unit 606 receives the third input data X2 and the operation result of the exclusive-OR operation unit 605, executes the exclusive-OR operation per bit between the third input data X2 and the operation result, and outputs the third output data Y2; an exclusive-OR operation unit 607 which is connected to the exclusive-OR operation unit 606, where the exclusive-OR operation unit 607 receives the fourth input data X3 and the operation result of the exclusive-OR operation unit 606, executes the exclusive-OR operation per bit between the fourth input data X3 and the operation result, and outputs the fourth output data Y3; and a data concatenation unit 608 which is connected to the exclusive-OR operation units 604˜607, where the data concatenation unit 608 concatenates the first˜fourth output data Y0˜Y3, and outputs the expansion key SK. Details of the process executed in each unit are described in the following explanations of the encryption process.
The following briefly describes the encryption process of the Rijndael encryption method executed by the encryption device 1300. As indicated in FIG. 16, the expansion key generating unit 6 outputs the encryption key EK as the expansion key SK0 to the key adding unit 500 within the data scrambling unit 5. The key adding unit 500 executes the exclusive-OR operation per bit between the plain text PT and the expansion key SK0 and outputs its result to the data conversion unit 50. The data dividing unit 600 divides the encryption key EK by each 32 bits from its upper bit into four data blocks D0, D1, D2 and D3.
Data entered into the data conversion unit 50 is sequentially processed for data conversion in each data conversion unit in the order from the data conversion unit 50 to the data conversion unit 58, and a result finally processed in the final data conversion unit 59 is output as the ciphertext CT.
Each of the data conversion units 50˜58 executes the data conversion process based on the expansion keys SK1˜SK9. Also, the final data conversion unit 59 executes the data conversion process based on the expansion key SK10. Each of the expansion keys SK1˜SK10 is generated in each of the key conversion units 60˜69 within the expansion key generating unit 6, and respectively provided to the data conversion units 50˜58 and the final data conversion unit 59 in the data scrambling unit 5. That is to say, there is a processing group at each stage, which consists of following processes (1) and (2) as a pair, and the data scrambling unit 5 executes 10 stages of them and generates the ciphertext CT.
Each of the key conversion units 60˜69 receives the first˜fourth input data X0˜X3 (32 bits each), executes the key conversion process, and outputs the expansion key SK (128 bits) and the first˜fourth output data Y0˜Y3. The data rotation unit 601, the data substituting unit 602 and the exclusive-OR operation unit 603 calculate the data T by conducting the operation expressed as the following formula (1) to the fourth input data X3.T=Rcon(+)Perm(ROTL8(X3))  (1)Here, ROTL8 (X) indicates a result of the rotation bit shift by 8 bits executed to the data X in the upper bit direction (the left direction). Perm (X) indicates a result of a specific substituting process executed to the data X. An operator “(+)” indicates the exclusive-OR operation per bit. The constant Rcon is 32-bit fixed value data which is different in each key conversion units 60˜69.
Each of the exclusive-OR operation units 604˜607 executes the operation indicated in the following formulas (2)˜(5) using the data T resulted from above, and finds the respective first˜fourth output data Y0˜Y3.Y0=T(+)X0  (2)Y1=Y0(+)X1  (3)Y2=Y1(+)X2  (4)Y3=Y2(+)X3  (5)
The data concatenation unit 608 gets the expansion key SK containing a relation expressed in the following formula (6). The operator “∥” indicates data concatenation. That is to say, the below formula (6) shows the 128-bit expansion key SK can be found by concatenating the first˜fourth output data Y0˜Y3 having 32 bits each.SK=Y0∥Y1∥Y2∥Y3  (6)
Each of the key conversion units 60˜69 outputs the expansion key SK and the first˜fourth output data Y0˜Y3 obtained as a result of the above process.
FIG. 18 is a diagram to show the internal structure of the decryption device using the Rijndael encryption method. A decryption device 1400 includes the following elements: an expansion key inverse generating unit 8 that generates the expansion keys SK10˜SK0 of 128 bits each in a reverse order of encryption, which is from the 128-bit encryption key EK; and a data inverse scrambling unit 7 that is connected to the expansion key inverse generating unit 8, receives the expansion keys SK10˜SK0 from the expansion key inverse generating unit 8, executes a specific inverse data scrambling process to the 128-bit ciphertext using the expansion keys SK10˜SK0, and outputs the decryption text DT.
The expansion key inverse generating unit 8 includes the following elements: a data dividing unit 800 which receives the encryption key EK and divides it by each 32 bits from its upper level into four data blocks; a key conversion unit 80 which is connected to the data dividing unit 800, where the key conversion unit 80 receives the four blocks, executes a specific operation to them and outputs four 32-bit data blocks; key conversion units 81˜88, each of which is connected to the preceding key conversion unit, where each key conversion unit 81˜88 receives four 32-bit data blocks from the preceding key conversion unit, executes a specific operation to them, generates and outputs four 32-bit data blocks to the next key conversion unit; and a key conversion unit 89 which is connected to the key conversion unit 88, where the key conversion unit 89 receives four 32-bit data blocks from the key conversion unit 88, executes a specific operation to the four 32-bit data blocks, and generates and outputs the expansion key SK10 and four 32-bit data blocks.
Since the specific operation executed by the key conversion units 80˜89 is the same as the specific operation executed by the key conversion units 60˜69 respectively, each of the key conversion units 80˜89 has the same structure as the key conversion unit indicated in FIG. 17. Therefore, they are not explained here in detail.
However, the key conversion units 80˜88 do not output the expansion keys SK1˜SK9, which are different from the key conversion units 60˜68. Because of this, each of the key conversion units 80˜88 may have the structure of the key conversion unit shown in FIG. 17 where the data concatenation unit 608 is excluded.
The expansion key inverse generating unit 8 further includes the following elements: a key inverse conversion unit 90 which is connected to the key conversion unit 89, where the key conversion unit 90 receives four 32-bit data blocks output from the key conversion unit 89, executes a key inverse conversion process, which is explained later, generates and outputs the expansion key SK9 and four 32-bit data blocks, and key inverse conversion units 91˜99, each of which is connected to the key inverse conversion unit, where each of the inverse conversion units 91˜99 receives four 32-bit data blocks from the preceding key inverse conversion unit, executes the key inverse conversion process, which is explained later, generates and outputs the expansion key and four 32-bit data blocks.
Each of the expansion keys output from the key inverse conversion units 90˜99 are the respective expansion keys SK9˜SK0. The key inverse conversion unit 99 outputs four data blocks, but they are not used for other processes.
The data inverse scrambling unit 7 includes the following elements: a final data inverse conversion unit 70 which is connected to the key conversion unit 89, where the final data inverse conversion unit 70 receives the expansion key SK10 from the key conversion unit 89, executes an inverse conversion process of the conversion process executed by the final data conversion unit 59 using the ciphertext CT and the expansion key SK10, and outputs the process result; and a data inverse conversion unit 71 which is connected to the final data inverse conversion unit 70 and the key inverse conversion unit 90, where the data inverse conversion unit 71 respectively receives the process result and the expansion key SK9 from the final data inverse conversion unit 70 and the key inverse conversion unit 90, executes the inverse conversion process of the conversion process executed by the data conversion unit 58, and outputs the process result.
The data inverse scrambling unit 7 further includes the following elements: data inverse conversion units 72˜79, each of which is connected to the preceding data inverse conversion unit respectively and also connected the key inverse conversion units 91˜98 respectively, where each of the date inverse conversion units 72˜79 receives the expansion keys SK8˜SK1 respectively from the key inverse conversion units 91˜98, executes respectively the inverse conversion process of the conversion process executed by the data conversion units 57˜50, and outputs the process result; and a key adding unit 700 which is connected to the data inverse conversion unit 79 and the key inverse conversion unit 99, where the key adding unit 700 receives the process result and the expansion key SK0 respectively from the data inverse conversion unit 79 and the key inverse conversion unit 99, executes the inverse conversion process of the conversion process executed in the key adding unit 500, and outputs the decryption text DT.
FIG. 19 is a diagram to show each internal structure of the key inverse conversion units 90˜99. Each of the key inverse conversion units 90˜99 executes the key inverse conversion process, which is equivalent to the inverse conversion of the key conversion process executed respectively in each of the key conversion units 60˜69 and 80˜89 based on the first˜fourth input data Y0˜Y3, which is 32 bits each, and outputs the first˜fourth output data Z0˜Z3 and the 128-bit expansion key SK.
Each of the key inverse conversion units 90˜99 includes following units: an exclusive-OR operation unit 901 that executes the exclusive-OR operation per bit between the third input data Y2 and the fourth input data Y3, and outputs the fourth output data Z3; an exclusive-OR operation unit 902 that executes the exclusive-OR operation per bit between the second input data Y1 and the third input data Y2, and outputs the third output data Z2; and an exclusive-OR operation unit 903 that executes the exclusive-OR operation per bit between the first input data Y0 and the second input data Y1, and outputs the second output data Z1.
Each of the key inverse conversion units 90˜99 further includes the following elements: a data rotation unit 905 which is connected to the exclusive-OR operation unit 901, receives an output of the exclusive-OR operation unit 901, where each of the key inverse conversion units 90˜94 executes the rotation bit shift by 8 bits to the output in the upper bit direction (the left direction), and outputs the result; and a data substituting unit 906 which is connected to the data rotation unit 905, where the data rotation unit 905 receives the operation result from the data rotation unit 905, executes a specific substituting process to the operation result, and outputs the result.
Each of the key inverse conversion units 90˜99 further includes the following elements: an exclusive-OR operation unit 907 that is connected to the data substituting unit 906, where the exclusive-OR operation unit 907 receives the substituting result from the data substituting unit 906, executes the exclusive-OR operation per bit between the substituting result and a 32-bit constant Rcon predefined in each of the key inverse conversion units 90˜99, and outputs data T; an exclusive-OR operation unit 904 which is connected to the exclusive-OR operation unit 907, where the exclusive-OR operation unit 904 receives the data T from the exclusive-OR operation unit 907, executes the exclusive-OR operation per bit between the first input data Y0 and the data T, and outputs the first output data Z0; and a data concatenation unit 908 which is connected to the exclusive-OR operation units 904˜901, where the data concatenation unit 909 concatenates the first˜fourth output data Z0˜Z3, and outputs the expansion key SK. Details of the process taken in each unit are described in the following explanation of a decryption process.
The following briefly describes the decryption process of the Rijndael encryption method executed by the decryption device 1400. As shown in FIG. 18, the data dividing unit 800 divides the 128-bit encryption key EK by each 32 bits from its upper bit into four 32-bit data blocks. A key conversion process is sequentially executed based on these four data blocks in the key conversion units 80˜89. As mentioned above, the key conversion process executed in the key conversion units 80˜89 is the same as the key conversion process done in the key conversion units 60˜69 indicated in FIG. 16. However, the expansion keys SK1˜SK9 respectively generated in the key conversion units 80˜88 are not used for any subsequent processes.
A key conversion unit 89 outputs the generated expansion key SK to the final data inverse conversion unit 70 as the expansion key SK10. Subsequently, each of the key inverse conversion units 90˜99 generates the respective expansion keys SK9˜SK0 in order. In parallel with the processes executed in the key conversion unit 89 and the key inverse conversion units 90˜99, the final data inverse conversion unit 70, the data inverse conversion units 71˜79 and key adding unit 700 execute a specific process respectively based on the expansion keys SK10˜SK0. The key adding unit 700 finally generates the decryption text DT, and outputs it.
Next, the following describes details of a process executed in the data inverse scrambling unit 7. The process done in the data inverse scrambling unit 7 is equivalent to inverse conversion of the process taken place in the data scrambling unit 5 of the encryption device 1300 indicated in FIG. 16. Initially, the final data inverse conversion unit 70 executes the inverse conversion process of the process carried out by the final data conversion unit 59 with the expansion key SK10. Subsequently, the data inverse conversion units 71˜79 respectively conduct the inverse conversion process of the process in the data conversion units 58˜50 using the respective expansion keys SK9˜SK1. Lastly, the key adding unit 700 executes the inverse conversion process of the process executed in the key adding unit 500 using the expansion key SK0 and generates the decryption text DT, and outputs it. As mentioned above, at the time of decryption, it is necessary to generate the expansion key in a reverse order of the encryption processes.
The following describes the key inverse conversion process executed in each of the key inverse conversion units 90˜99 indicated in FIG. 19.
Each of the exclusive-OR operation units 901˜903 finds the respective second˜fourth output data Z1˜Z3 by executing each operation shown in the following formulas (7)˜(9).Z1=Y0(+)Y1  (7)Z2=Y1(+)Y2  (8)Z3=Y2(+)Y3  (9)
The data rotation unit 905, the data substituting unit 906 and the exclusive-OR operation unit 907 calculate the data T by executing the operation indicated in the following formula (10) for the fourth output data Z3.T=Rcon(+)Perm(ROTL8(Z3))  (10)
The exclusive-OR operation unit 904 finds the first output data Z0, which is the exclusive-OR operation per bit between the data T and the first input data Y0 according to the next formula (11).Z0=T(+)Y0  (11)
The data concatenation unit 908 concatenates the first˜fourth output data Z0˜Z3 according to the next formula (12), and generates the 128-bit expansion key SK.SK=Z0∥Z1∥Z2∥Z3  (12)
Each of the key inverse conversion units 90˜99 outputs the expansion key SK resulted from the above process and the first˜fourth output data Z0˜Z3.
As shown in FIG. 17, the data substituting unit 602 executes a non-linear process at the time of encryption according to this method. There is an impact on the expansion key SK and all of the output data from the data processed by the non-linear process via the exclusive-OR operation units 604˜607. Therefore, though this method is a simple key conversion process, it can generate a highly random expansion key.
(Second Related Art)
The U.S. standard known as the Data Encryption Standard (DES) is the second related art. FIG. 20 is a diagram showing the structure of the key conversion unit 10 used by an encryption device in the DES method. A key conversion unit 10 includes rotation shift units 101 and 102, a data concatenation unit 103 which is connected to the rotation shift units 101 and 102, and a data degenerating unit 104 which is connected to the data concatenation unit 103.
The following describes actions of the key conversion unit 10. The rotation shift unit 101 executes a rotation bit shift process by a specific number of bits to 28-bit first input data, and generates first rotation shift data. The rotation shift unit 102 executes the rotation bit shift process by a specific number of bits to 28-bit second input data, and generates second rotation shift data. The first rotation shift data and the second rotation shift data are output as first output data and second output data respectively from the key conversion unit 10. On the other hand, the data concatenation unit 103 concatenates the first rotation shift data and the second rotation shift data to make 56-bit data, and outputs the data to the data degenerating unit 104. The data degenerating unit 104 extracts data for 48 bits at a predefined bit location from the input data, and outputs the expansion key.
According to the encryption device in the DES method the same expansion key generation process can be applied to generate the expansion key both at the encryption process and at the decryption process because generating the expansion key is basically realized by a data shift process and a data extraction process. Accordingly, there is no difference between the encryption and the decryption processes regarding the processing workload necessary for generating the expansion key.
The above mentioned inventions as well as other related inventions contain deficiencies. In regards to the encryption method of the first related art, the time required to execute the generating process for the expansion key at the decryption stage is greater than the time required at the encryption stage. These timing differences occur for the following reasons. As shown in FIG. 16, in the data scrambling unit 5 of the encryption device 1300, the encryption key EK is used as is in the key adding unit 500 that executes the first process. Therefore, a process of the data scrambling unit 5 can be executed in parallel with a process of the expansion key generating unit 6.
On the other hand, as indicated in FIG. 18, within the data inverse scrambling unit 7 of the decryption device 1400, the final data inverse conversion unit 70, which executes the process at first, must use the expansion key SK10 provided from the expansion key inverse generating unit 8. In order to get the expansion key SK10, a key conversion process needs to be carried out in the key conversion units 80˜89. That is to say, the final data inverse conversion unit 70 can start its process only after the key conversion process is executed 10 times. Therefore, the decryption process takes more time than the time taken for the encryption process because these key conversion processes must take place.
When the above-described time gap is significantly large, the following problems arise. Consider, for example, a communication system where data is exchanged in a real time manner between a receiving device and a sending device. If the encryption device 1300 and the decryption device 1400 explained in the first related art are used in such a communication system, the sending device can encrypt data and send it in a real time manner. However, the receiving device cannot decrypt the encryption message in a real time manner because the decryption takes time. Accordingly, the prior art requires the use of a margin at the receiving device to temporarily store the encrypted data, which increases the cost of the receiving device.
Also, as shown in FIG. 21, where an Electronic Toll Collection (ETC) system 1800 installed to a tollgate of expressways, data communication takes place between a tollgate antenna 1804 and an in-vehicle device 1802 which is attached to an automobile 1801 and authentication is executed between the tollgate antenna 1804 and the in-vehicle device 1802. Because the automobile 1801 normally travels through the gate of the ETC system 1800 without stopping, a high-speed response is required for the ETC system 1800. Therefore, if the conventional encryption device 1300 and decryption device 1400 are used in the ETC system 1800, high-speed hardware will be required.
On the other hand, the problem of the first related art, being “the time required to generate the expansion key at the decryption takes longer than the time at the encryption”, is resolved in the second related art. However, the second related art still contains a problem where the expansion key is not sufficiently at random.
In the second related art, data is treated as an expansion key wherein a certain number of bits at a specific position are extracted from the concatenated data after a rotation bit shift is applied. Since a data combining process or a substituting process is not used for a process to generate the expansion key, the expansion key is not adequately random. Regarding the generation process of the expansion key in the second related art, the key cannot maintain a high security level. This is typically called a “weak key”. The weak key in the DES method is described, for example, in “Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC Press, 1997, pp. 256–pp. 259”.